Search for: All records

Analog Ising machines (IMs) occupy an increasingly prominent area of computer architecture research, offering high-quality, low-latency, and low-energy solutions to intractable computing tasks; however, IMs have a fixed capacity, with little to no utility in out-of-capacity problems. Previous works have proposed parallel, multi-IM architectures to circumvent this limitation [A. Sharma, , in , ISCA ’22 (Association for Computing Machinery, New York, NY, USA, 2022), p. 508; R. Santos, , Enhancing quantum annealing via entanglement distribution, ArXiv:2212.02465]. In this work, we theoretically and numerically investigate trade-offs in parallel IM networks to guide researchers in this burgeoning field. We propose formal models of parallel IM execution models, and we then provide theoretical guarantees for probabilistic convergence. Numerical experiments illustrate our findings and provide empirical insights into the high- and low-synchronization-frequency regimes. We also provide practical heuristics for parameter and model selection, informed by our theoretical and numerical findings. 

. We present an oscillator model with both phase and amplitude dynamics for oscillator-based Ising machines (OIMs). The model targets combinatorial optimization problems with polynomial cost functions of arbitrary order and addresses fundamental limitations of previous OIM models through a mathematically rigorous formulation with a well-defined energy function and corresponding dynamics. The model demonstrates monotonic energy decrease and reliable convergence to low-energy states. Empirical evaluations on 3-SAT problems show significant performance improvements over existing phase-amplitude models. Additionally, we propose a flexible, generalizable framework for designing higher-order oscillator interactions, from which we derive a practical method for oscillator binarization without compromising performance. This work strengthens both the theoretical foundation and practical applicability of oscillator-based Ising machines for complex optimization problems. 

Dynamical solvers for combinatorial optimization are usually based on 2superscript{nd} degree polynomial interactions, such as the Ising model. These exhibit high success for problems that map naturally to their formulation. However, SAT requires higher degree of interactions. As such, these quadratic dynamical solvers (QDS) have shown poor solution quality due to excessive auxiliary variables and the resulting increase in search-space complexity. Thus recently, a series of cubic dynamical solver (CDS) models have been proposed for SAT and other problems. We show that such problem-agnostic CDS models still perform poorly on moderate to large problems, thus motivating the need to utilize SAT-specific heuristics. With this insight, our contributions can be summarized into three points. First, we demonstrate that existing make-only heuristics perform poorly on scale-free, industrial-like problems when integrated into CDS. This motivates us to utilize break counts as well. Second, we derive a relationship between make/break and the CDS formulation to efficiently recover break counts. Finally, we utilize this relationship to propose a new make/break heuristic and combine it with a state-of-the-art CDS which is projected to solve SAT problems several orders of magnitude faster than existing software solvers.